package subject_set.offer100;

/**
 * @author haomin
 * @date 2022/10/13 21:32
 **/
public class Offer12 {
    class Solution {
        public boolean exist(char[][] board, String word) {
            int m = board.length, n = board[0].length;
            for(int i = 0; i < m; ++i){
                for(int j = 0; j < n; ++j){
                    if(board[i][j] == word.charAt(0)){
                        if(isTrue(board, m, n, i, j, word, 0))
                            return true;
                    }
                }
            }
            return false;
        }
        private boolean isTrue(char[][] board, int m, int n, int i, int j, String word, int k) {
            if (k >= word.length()) return true;
            if (i < 0 || i >= m || j < 0 || j >= n ||
                    board[i][j] != word.charAt(k)) return false;

            board[i][j] += 58;
            boolean res = isTrue(board, m, n, i + 1, j, word, k + 1) ||
                    isTrue(board, m, n, i - 1, j, word, k + 1) ||
                    isTrue(board, m, n, i, j + 1, word, k + 1) ||
                    isTrue(board, m, n, i, j - 1, word, k + 1);
            board[i][j] -= 58;
            return res;
        }
    }
}